Trie树（小）总结Bycellur925

关于\(Trie\)树的详细介绍&＃xff0c;还请移步这篇深度好文

插入

void insert(){int p&＃61;0;int len&＃61;strlen(tmp&＃43;1);for(int i&＃61;1;i}

注意&＃xff0c;其中\(tot&＃61;0\)&＃xff0c;我习惯\(p\)初始值也为\(0\)。\(tot\)与\(p\)初值应保持一致。

检索操作非常灵活&＃xff0c;各题不同&＃xff0c;但是都很简单&＃xff0c;那么就自己想吧&＃61;w&＃61;&＃xff08;不负责地逃离&＃xff09;。

在每个文章记录一下出现次数即可。

#include#include#includeusing namespace std;int n,m,l,p,tot&＃61;1;int trie[500090][26];bool b[500000][1100];char word[25];void insert(char *str,int opt){int len&＃61;strlen(str);p&＃61;1;for(int k&＃61;0;k}void ask(char *str){int len&＃61;strlen(word);p&＃61;1;bool flag&＃61;1;for(int k&＃61;0;k} int main(){scanf("%d",&n);for(int i&＃61;1;i}

给定\(n\)个长度不超过\(10\)的数字串&＃xff0c;判断是否有两个字符串\(A\)和\(B\),满足\(A\)是\(B\)的前缀。

满足题目中的条件对于每个串有两种情况&＃xff1a;当这个串没读完的时候&＃xff0c;有字符串以当前指针为结尾&＃xff0c;说明之前串是当前串的前缀&＃xff1b;这个串读完后&＃xff0c;在计数数组中已经有记录&＃xff0c;说明当前串是之前串的前缀。第一种情况开始被我忽略了。

分析完这点后&＃xff0c;注意多组数据清空&＃xff0c;空间开合适就好了。但是这题特别坑&＃xff0c;存在的情况输出\(NO\)&＃xff0c;不存在输出\(YES\)。被坑了233.

#include#include#includeusing namespace std;int T,n,tot,lim;int trie[200900][20],endd[200090],cnt[200090];bool flag;char tmp[20];void in_trie(){int p&＃61;0,len&＃61;strlen(tmp&＃43;1);for(int i&＃61;1;i1) flag&＃61;1;}int main(){scanf("%d",&T);while(T--){flag&＃61;0;scanf("%d",&n);for(int i&＃61;1;i}

话说做这道题的时候开始用的数组叫\(end\)然后\(Compile\) \(error\)了...虚的一批。

非常符合字典树的性质&＃xff0c;直接上就行了。

#includeusing namespace std;int n,m,tot,p;int flag,end[1000090];int trie[1000090][27];char a[100];void insert(char *str){int len&＃61;strlen(str);p&＃61;1;for(int k&＃61;0;k}bool search(char *str){int len&＃61;strlen(str),p&＃61;1;for(int k&＃61;0;k}int main(){scanf("%d",&n);for(int i&＃61;1;i}

Luogu P4551 最长异或路径

给定一棵\(n\)个点的带权树&＃xff0c;结点下标从\(1\)开始到\(N\)。在树中找两个结点&＃xff0c;求最长的异或路径。

先考虑一个简化问题&＃xff1a;给你一个数列&＃xff0c;在其中任选两个数异或&＃xff0c;求能获得的异或最大值。

考虑把\(32\)位的二进制\(01\)串强行塞到\(trie\)树上&＃xff0c;这个树上的所有元素只可能为\(0\)或\(1\)。那么我们可以对于每个元素&＃xff0c;在字典树上进行检索&＃xff0c;每次尝试访问与这个元素的这个位的相反的指针&＃xff0c;若指针指向空&＃xff0c;那么只能访问和这位相同的指针。因为异或运算时“相同得1不同得0”的&＃xff0c;所以这样能保证最优。

回到我们原来的问题之前&＃xff0c;我们看另一道题&＃xff1a;Luogu P2420 让我们异或吧。求两点间路径的所有边权的异或值。设\(d[i]\)为根节点到当前节点路径上的异或值。那么对于\((x,y)\)答案就是\(d[x]\) \(xor\) \(d[y]\)。为什么不用考虑他们的\(lca\)以上的部分呢&＃xff0c;以为他们相同&＃xff0c;一异或就会变成0了&＃61;&＃61;。

代码还是稍微给一下&＃xff1f;&＃xff08;虽然和今天的内容关系不大&＃xff09;

#includeusing namespace std;int n,m,tot;int head[200009];int xxor[200009],visit[200009];struct node{int to,val,next;}edge[200009];queueq;void add(int x,int y,int z){edge[&＃43;&＃43;tot].to&＃61;y;edge[tot].val&＃61;z;edge[tot].next&＃61;head[x];head[x]&＃61;tot;}void bfs(){//queueq;q.push(1);visit[1]&＃61;1;while(!q.empty()){int x&＃61;q.front();q.pop();for(int i&＃61;head[x];i;i&＃61;edge[i].next){int y&＃61;edge[i].to;if(visit[y]) continue;visit[y]&＃61;1;xxor[y]&＃61;xxor[x]^edge[i].val;q.push(y);}}}int main(){scanf("%d",&n);for(int i&＃61;1;i}

回到我们最开始的问题&＃61;&＃61;&＃xff01;有了前面两题的基础&＃xff0c;那么我们在这个问题中要求的答案就等效于简化问题&＃xff0c;只是数列变成了\(d[]\)。

#include#includeusing namespace std;int n,tot,ans;int d[100090],head[100090],trie[100090*32][5];struct node{int to,next,val;}edge[200090];void add(int x,int y,int z){edge[&＃43;&＃43;tot].to&＃61;y;edge[tot].next&＃61;head[x];head[x]&＃61;tot;edge[tot].val&＃61;z;}void dfs(int u,int fa){for(int i&＃61;head[u];i;i&＃61;edge[i].next){int v&＃61;edge[i].to;if(v&＃61;&＃61;fa) continue;d[v]&＃61;d[u]^edge[i].val;dfs(v,u);}}void insert(int x){int p&＃61;0;for(int i&＃61;(1>&＃61;1){bool qwq&＃61;x&i;//注意用bool if(!trie[p][qwq]) trie[p][qwq]&＃61;&＃43;&＃43;tot;p&＃61;trie[p][qwq];}}int ask(int x){int p&＃61;0,orz&＃61;0;for(int i&＃61;(1>&＃61;1){bool qwq&＃61;x&i;if(trie[p][qwq^1]) orz&＃43;&＃61;i,p&＃61;trie[p][qwq^1];else p&＃61;trie[p][qwq];}return orz;}int main(){scanf("%d",&n);for(int i&＃61;1;i}

一定要注意\(qwq\)是\(bool\)类型的&＃xff01;这样保证只有0或1。如果是\(int\)的话&＃xff0c;就不保证了&＃xff01;&＃xff01;&＃xff08;\(Warning\)&＃xff09;

讨论下开空间的问题吧&＃xff01;

本蒟蒻几乎是做一道\(trie\)就\(RE\)一次...&＃xff08;逃&＃xff09;

比较玄学...尽量开大一点好&＃xff08;逃&＃xff09;